/**
 * Universidad Del Valle De Guatemala.
 * Algoritmos y Estructuras de Datos.
 * Sección 20.
 * Miguel Enrique Zea Arenales.
 * Carné 09238.
 * 20/09/2012.
 */
package heapshuffman;

import java.util.ArrayList;

/**
 * @author Miguel Zea
 * Implementación de un árbol binario de Huffman. 
 * Tomado del texto Java Structures de Duane A. Bailey capítulo 12.
 * http://www.cs.williams.edu/JavaStructures/Book.html
 */
class HuffmanTree implements Comparable<HuffmanTree> {
    BinaryTree<HuffmanNode> empty;
    BinaryTree<HuffmanNode> root; // Raíz del árbol.
    int totalWeight;     // Peso del árbol.

    /**
     * @pre Ninguna.
     * @post Construye un nodo del caracter asociado. 
     */
    public HuffmanTree(HuffmanNode e) {
        empty = new BinaryTree<HuffmanNode>();
        root = new BinaryTree<HuffmanNode>(e, empty, empty);
        totalWeight = e.frequency;
    }

    /**
     * @pre Left y Right son árboles de Huffman no nulos.
     * @post Mezcla ambos árboles y sus respectivos pesos. 
     */
    public HuffmanTree(HuffmanTree left, HuffmanTree right) {
        this.totalWeight = left.totalWeight + right.totalWeight;
        root = new BinaryTree<HuffmanNode>(new HuffmanNode(this.totalWeight), left.root, right.root);
    }

    /**
     * @pre El objeto a comparar es no nulo.
     * @post Regresa un entero que refleja la relacion entre los pesos. 
     */
    public int compareTo(HuffmanTree other) {
        HuffmanTree that = (HuffmanTree)other;
        return this.totalWeight - that.totalWeight;
    }

    /**
     * @pre El objeto a comparar es no nulo.
     * @post Regresa verdadero si los objetos comparados el mismo. 
     */
    public boolean equals(Object that) {
        return this == that;
    }
    
    /**
     * @pre Ninguna.
     * @post Imprime cadenas asociadas a los caracteres en el árbol. 
     */
    public void print(ArrayList encoding) {
        print(this.root, "", encoding);
    }

    /**
     * @pre Ninguna.
     * @post Imprime cadenas asociadas a los caracteres en el árbol, al igual que
     * su codificación respectiva. 
     */
    protected void print(BinaryTree<HuffmanNode> r, String representation, ArrayList encoding) {
        if (!r.left().isEmpty()) {   // Nodo interior.
            print(r.left(),representation+"0", encoding); // Se agrega un 0
            print(r.right(),representation+"1", encoding); // Se agrega un 1
        } else { // Nodo; Se imprime la codificación
            HuffmanNode e = r.value();
            HuffmanCode hc = new HuffmanCode(e.ch, representation);
            encoding.add(hc);
            //System.out.println("Encoding of "+e.ch+" is "+ representation+" (frequency was "+e.frequency+")");
        }
    }
}
